import org.junit.Test

//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3794 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionLongestPalindrome {
    @Test
    fun main() {
        // longestPalindrome("abba")
        // longestPalindrome("bb")
        longestPalindrome("aacabdkacaa")
    }

    /***
     * 回文串，向两边扩散查找。
     */
    fun longestPalindrome(s: String): String {
        return getLongestPalindrome(s);
    }

    private fun getLongestPalindrome(s: String): String {
        var dp = Array(s.length) { BooleanArray(s.length) }
        var max = 0;
        // if (s.length > 0) {
        //     max = 1;
        // }
        var leftMax = 0
        /***
         * 单个字符都是回文子子串
         */
        // for (i in s.indices) {
        //     dp[i][i] = true;
        // }

        // 子串后续用到前者，因此先从长度为2开始推
        // 子串长度
        for (length in 1 until s.length + 1) {
            for (left in s.indices) {
                var right = length + left - 1
                if (right >= s.length) {
                    break
                }
                if (s.get(left) != s.get(right)) {
                    dp[left][right] = false
                } else {
                    // 长度3个以内，且左右相等即为回文
                    if (right - left + 1 <= 3) {
                        dp[left][right] = true
                    } else {
                        dp[left][right] = dp[left + 1][right - 1]
                    }
                }
                // 找到一个回文子串
                if (dp[left][right]) {
                    if (max < right - left + 1) {
                        max = right - left + 1
                        leftMax = left;
                    }
                }
            }
        }
        // for (i in s.indices) {
        //     for (j in s.indices) {
        //         print(dp[i][j])
        //         print("\t")
        //     }
        //     println()
        // }
        println("" + max + "\t" + leftMax)
        val palindrome = s.substring(leftMax, leftMax + max)
        println(palindrome)
        return palindrome
    }
}
//leetcode submit region end(Prohibit modification and deletion)
